Panduan C++ Edisi Kelima: Di Luar Pencarian Linier: Kekuatan Kontainer Asosiatif

Bayangkan sebuah perpustakaan di mana buku-buku tidak disusun berdasarkan tanggal kedatangan, tetapi berdasarkan Kunci Universal. Ini adalah perubahan paradigma dari urutan ke Kontainer Asosiatif. Alih-alih memindai sebuah vektor secara linier ($O(N)$), kita menggunakan peta atau set untuk mencapai pencarian dengan waktu logaritmik ($O(\log n)$).

1. Sifat Asosiasi

Dalam sebuah peta, kita menyimpan pasangan kunci-nilai. Kunci bertindak sebagai indeks yang bisa berupa string, objek khusus, atau tipe apa pun yang mendukung Urutan Lemah Ketat. Sebuah set, sebaliknya, hanya menyimpan kunci unik, menjadikannya alat sempurna untuk pengujian keanggotaan atau penyaringan.

2. Berurutan vs. Tidak Berurutan

Kontainer standar (peta, set) menyimpan kunci secara terurut. Standar C++11 memperkenalkan varian tidak berurutan (unordered_map) yang menggunakan fungsi hash untuk kinerja rata-rata $O(1)$. Cari logo Logo C++11 saat menggunakan ember-ember performa tinggi ini.

TERMINALbash — 80x24

> Ready. Click "Run" to execute.

QUESTION 1

What happens when you use the subscript operator m[k] on a map if the key k does not exist?

It throws an out_of_range exception.

It returns a null pointer.

It adds a new element with key k and a value-initialized value.

The program fails to compile.

❌ Incorrect

Unlike at(), the [] operator is an insertion-on-demand mechanism.

QUESTION 2

Which of the following calls is ILLEGAL for a multiset c and a vector v?

copy(v.begin(), v.end(), inserter(c, c.end()));

copy(v.begin(), v.end(), back_inserter(c));

copy(c.begin(), c.end(), back_inserter(v));

copy(c.begin(), c.end(), inserter(v, v.end()));

✅ Correct!

Correct. back_inserter requires push_back, which associative containers like multiset do not support.

❌ Incorrect

Associative containers lack push_back, so back_inserter cannot be used with them.

QUESTION 3

Identify the correct way to define a variable to hold the result of calling find on a map<string, vector>>.

vector<int> res = m.find("key");

map<string, vector>::iterator it = m.find("key");>

pair<string, vector> p = m.find("key");>

bool found = m.find("key");

✅ Correct!

find returns an iterator to the element if found, or m.end() otherwise.

❌ Incorrect

The find method always returns an iterator, not the value or a boolean.

QUESTION 4

What is the primary advantage of using a set over a vector for storing a list of excluded words?

A set uses less memory than a vector.

A set allows for duplicate excluded words.

A set provides O(log N) lookup instead of O(N) linear search.

A set allows elements to be accessed by index.

✅ Correct!

Using exclude.find(word) on a set is significantly more efficient than std::find on a vector for large datasets.

QUESTION 5

In the expression ++word_count.insert({word, 0}).first->second;, what does first refer to?

The key of the inserted element.

The boolean indicating if insertion was successful.

An iterator to the element with the given key.

The first element in the entire map.

✅ Correct!

map::insert returns a pair where first is an iterator to the element.

❌ Incorrect

The return of insert is a pair<iterator, bool>. first is the iterator.